/**
 * @author: lk
 * @data: 2021/11/11 15:00
 */
package LeetCode;

public class _704 {
    public static  int searchR(int[] data, int target) {
        return searchR(data, 0, data.length - 1, target);
    }

    private static  int searchR(int[] data, int l, int r, int target) {
        if (l > r)
            return -1;
        int mid = l + (r - l) / 2;
        if (data[mid] == target)
            return mid;
        else if (data[mid] < target )
            return searchR(data, mid + 1, r, target);
        return searchR(data, l, mid - 1, target);
    }

    public static  int search(int[] data, int target) {
        int l = 0, r= data.length-1;
        //[l,r]中寻找
        while (l <= r) {
            int mid = l+(r-l)/2;
            int x = data[mid];
            if(x==target)
                return mid;
            else if(x < target)
                l=mid+1;
            else
                r=mid-1;
        }
        return -1;
    }

    /**
     * 换了循环不变量的迭代版本。这次是在[l,r)中寻找。因此需要改的只有一处：更新r那一句。
     * [l,r]中的版本是r=mid+1;
     * [l,r)的版本是 r=mid;
     * @param data
     * @param target
     * @return
     */
    public static int search2(int[] data, int target) {
        int l=0,r=data.length;
        //[l,r)中寻找。
        while (l < r) {
            int mid = l+(r-l)/2;
            if(data[mid] == target)
                return mid;
            else if(data[mid] < target)
                l=mid+1;
            else
                 r=mid;
        }
        return -1;
    }
}


